package lcof;

/**
 * @author 江岸
 * @version V1.0
 * @ClassName: MyPow16
 * @description: 实现函数double Power(double base, int exponent)，求base的exponent次方。不得使用库函数，同时不需要考虑大数问题。
 *
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode-cn.com/problems/shu-zhi-de-zheng-shu-ci-fang-lcof
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 * @date 2021/3/510:18
 * @since V1.0
 */
public class MyPow16 {

    public double myPow(double x, int n) {
        if(n==0 || x==1){
            return 1;
        }
        if(n == 1) return 1 ;
        if(n == -1) return 1 / x;
        double res = 1;
        for (int i=0;i<Math.abs(n);i++){
            res = res * x;
        }
        if (n>0) return res;
        return  1/res;
    }

    public static void main(String[] args) {
        int n = -2147483648;

        myPow2(2,10);
    }

    /**二分法 快速幂
     * 二分推导： xn=xn/2×xn/2=(x2)n/2x^n = x^{n/2} \times x^{n/2} = (x^2)^{n/2}xn=xn/2×xn/2=(x2)n/2 ，令 n/2n/2n/2 为整数，则需要分为奇偶两种情况（设向下取整除法符号为 "//////" ）：
     *
     *     当 nnn 为偶数： xn=(x2)n//2x^n = (x^2)^{n//2}xn=(x2)n//2 ；
     *     当 nnn 为奇数： xn=x(x2)n//2x^n = x(x^2)^{n//2}xn=x(x2)n//2 ，即会多出一项 xxx ；
     *
     *
     * 根据二分推导，可通过循环 x=x2x = x^2x=x2 操作，每次把幂从 nnn 降至 n//2n//2n//2 ，直至将幂降为 000 ；
     * 设 res=1res=1res=1 ，则初始状态 xn=xn×resx^n = x^n \times resxn=xn×res 。在循环二分时，每当 nnn 为奇数时，将多出的一项 xxx 乘入 resresres ，则最终可化至 xn=x0×res=resx^n = x^0 \times res = resxn=x0×res=res ，返回 resresres 即可。
     *
     * 作者：jyd
     * 链接：https://leetcode-cn.com/problems/shu-zhi-de-zheng-shu-ci-fang-lcof/solution/mian-shi-ti-16-shu-zhi-de-zheng-shu-ci-fang-kuai-s/
     * 来源：力扣（LeetCode）
     * 著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
     */
    //用例-2147483648 在int[-2147483648,2147483647] 之间，但取绝对值就超过范围了
    public static double myPow2(double x, int n){
        if (x==0) return 0;
        long b = n;
        if (b<0){
            x=1/x;
            b=-b;
        }
        double res = 1.0;
        while (b>0){
            if ((b&1)==1){
                //b为奇数 即b%2==1
                res = res * x;
            }
            x = x * x;
            b>>=1; //b = /2;
        }
        return res;
    }
}
